//双链表和循环链表作业
#include<stdio.h>
#include<malloc.h>

typedef int ElemType;

//双链表
typedef struct Dnode
{
	ElemType data;
	struct Dnode *prior,*next;
	int freq;
}DLinkNode;

//循环单链表
typedef struct LNode		//定义单链表结点类型
{
	ElemType data;
	struct LNode *next;
} LinkNode;


void CreateListR(DLinkNode *&L,ElemType a[],int n)
//尾插法建双链表
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		s->freq=0;
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}




void DestroyList(DLinkNode *&L)
{
	DLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}
//双链表展示
void DispList(DLinkNode *L)
{
	DLinkNode *p=L->next;
	while (p!=NULL)
	{
		printf("data:%d freq:%-5d\n",p->data,p->freq);
		p=p->next;
		
	}
	printf("\n");
}

//尾插法建立循环单链表
void CreateListRDan(LinkNode *&L,ElemType a[],int n)
{
	LinkNode *s,*r;int i;
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
		s->data=a[i];
		r->next=s;			//将结点s插入结点r之后
		r=s;
	}
	r->next=L;				//尾结点next域指向头结点
	
}


void DestroyListDan(LinkNode *&L)
{
	LinkNode *p=L,*q=p->next;
	while (q!=L)
	{
		free(p);
		p=q;
		q=p->next;
	}
	free(p);
}


//双链表任务
void Locatenode(DLinkNode *&L,ElemType x)
{
	if(L==NULL&&L->next==NULL) return;
	
	
	DLinkNode* p = L->next;
	DLinkNode* s = NULL;
	while(p!=NULL&&p->data!=x)
	{
		p = p->next;
	}
	
	if(p==NULL)
	{
		printf("没有%d这个元素!\n",x);
		return;
	}
	else{
		p->freq++;
		s = p;
		if(p->next!=NULL)
		{
			p->prior->next = p->next;
			p->next->prior = p->prior;
		}
		else if(p->next==NULL)
		{
			p->prior->next=NULL;
		}
		p = L;
		while(p->next!=NULL)
		{
			if(p->next->freq<=s->freq)
			{
				s->next = p->next;
				p->next->prior = s;
				s->prior = p;
				p->next = s;
				break;
			}
			p = p->next;
		}
	}

	

	

}

//双链表任务
void test01()
{
	DLinkNode* h;
	ElemType a[7] = {1,2,3,4,5,6,7};
	CreateListR(h,a,7);
	printf("任务一：\n");
	printf("初始化双链表：\n");	
	DispList(h);
	
	printf("--------------------------------\n");
	
	DLinkNode*p = h->next;
	for(int i=0;i<7;i++)
	{
		p->freq = 7-i;
		p = p->next;
	}
	Locatenode(h,7);
	DispList(h);
	
	DestroyList(h);//释放内存
}



void DispListDan(LinkNode *L)
{
	LinkNode *p=L->next;
	while (p!=L)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

//循环链表
void test02()
{
	LinkNode* L;
	ElemType a[6] = {1,3,3,5,7,8};
	CreateListRDan(L,a,6);//尾插法建立循环单链表
	ElemType m = 0;
	ElemType n = 0;
	printf("任务二：\n将有序循环单链表rear中值为e元素修改值为new_e，使其仍有序\n");
	printf("初始化后：循环单链表是：");
	DispListDan(L);
	printf("你要更改哪个元素的值：");
	scanf("%d",&m);
	printf("你要改成什么：");
	scanf("%d",&n);
	
	LinkNode* p = L->next;
	int flag = 1;
	while(p!=L)
	{
		if(p->data==m)
		{
			flag = 0;//表示更改了元素
			p->data = n;//更改为n
		}
		p = p->next;
	}
	if(flag==1)
	{
		printf("链表中没有你想要更改的元素\n");
	}
	else{
		//如果已经成功更改，现在就需要我们对单链表进行排序
		
		//排序操作
		LinkNode *cur,*nex;
		int len = 0;
		p = L;
		while(p->next!=L)
		{
			len++;
			p = p->next;
		}
		//printf("len = %d\n",len);
		
		for(int i = 0;i<len;i++)
		{
			p = L;
			cur = p->next;
			nex = cur->next;
			int flag = 1;
			while(cur->next!=L)
			{
				if(cur->data>nex->data)
				{
					flag = 0;
					cur->next = nex->next;
					nex->next = cur;
					p->next = nex;
				}
				p = p->next;
				cur = p->next;
				nex = cur->next;
			}
			
			if(flag==1)
			{
				break;//说明已经排好序了
			}
			
			
		}
		printf("排序结束之后：");
		DispListDan(L);
		
	}
	
	
	DestroyListDan(L);//释放内存
}

int main()
{
	//双链表
	test01();
	
	//循环链表
	test02();
	
	return 0;
}























